package zhengqc.graph.algorithm;


import zhengqc.graph.data_structure.Graph;

/* 无向图环检测
 * 适用于无向图 */
public class UndirectedCycleDetection {
    private Graph graph;
    private boolean[] visited;
    private boolean hasCycle;

    public UndirectedCycleDetection(Graph graph) {
        if (graph.isDirected()) {
            throw new IllegalArgumentException("UndirectedCycleDetection doesn't work in Directed-Graph");
        }
        this.graph = graph;
        this.visited = new boolean[graph.getV()];
        for (int v = 0; v < graph.getV(); ++v) {
            if (!visited[v]) {
                if (dfs(v, v)) {
                    this.hasCycle = true;
                    break;
                }
            }
        }
    }

    // 从顶点 v 开始, 判断图中是否有环
    private boolean dfs(int v, int parent) {
        this.visited[v] = true;
        for (int w: graph.getAdjacency(v)) {
            if (!visited[w]) { // w 没有被访问过
                if (dfs(w, v)) {
                    return true;
                }
            } // w 被访问过, 但 w 不是 v 的 parent, 则可以判断此图有环
            else if (w != parent) {
                return true;
            }
        }
        return false;
    }
    public boolean hasCycle() {
        return this.hasCycle;
    }
}
